import java.util.*;
//49. 字母异位词分组
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 使用哈希表来存储字母异位词分组
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            // 将每个字符串排序后作为键
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortedStr = new String(chars);

            // 将原始字符串加入对应的字母异位词组
            map.putIfAbsent(sortedStr, new ArrayList<>());
            map.get(sortedStr).add(str);
        }

        // 返回所有分组
        return new ArrayList<>(map.values());
    }
}


//面试题 03.06. 动物收容所
class AnimalShelf {
    Deque<int[]> catQueue;//猫
    Deque<int[]> dogQueue;//狗

    public AnimalShelf() {
        catQueue=new LinkedList<>();
        dogQueue=new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        int type=animal[1];
        if(type==1){
            dogQueue.offer(animal);
        }else{
            catQueue.offer(animal);
        }


    }

    public int[] dequeueAny() {
        if(dogQueue.isEmpty()&&catQueue.isEmpty()){
            return new int[]{-1,-1};
        }else if(dogQueue.isEmpty()){
            return catQueue.poll();
        }else if(catQueue.isEmpty()){
            return dogQueue.poll();
        }
        int[] arr=dogQueue.peek();
        int[] arr1=catQueue.peek();
        return arr[0]>arr1[0]?catQueue.poll():dogQueue.poll();
    }

    public int[] dequeueDog() {
        if(dogQueue.isEmpty()){
            return new int[]{-1,-1};
        }
        return dogQueue.poll();
    }

    public int[] dequeueCat() {
        if(catQueue.isEmpty()){
            return new int[]{-1,-1};
        }
        return catQueue.poll();
    }
}

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf obj = new AnimalShelf();
 * obj.enqueue(animal);
 * int[] param_2 = obj.dequeueAny();
 * int[] param_3 = obj.dequeueDog();
 * int[] param_4 = obj.dequeueCat();
 */